/*
 * @lc app=leetcode.cn id=912 lang=typescript
 *
 * [912] 排序数组
 */

// @lc code=start
function sortArray(nums: number[]): number[] {
  const merge = (arr: number[], l: number, r: number): void => {
    if (l >= r) return;
    let mid = l + ((r - l) >> 1);
    merge(arr, l, mid);
    merge(arr, mid + 1, r);

    // 临时数组，存储区间有序状态
    const temp = new Array(r - l + 1);
    let k = 0;
    let left = l;
    let right = mid + 1;
    while (left <= mid || right <= r) {
      if (right > r || (left <= mid && nums[left] <= nums[right])) {
        temp[k++] = nums[left++];
      } else {
        temp[k++] = nums[right++];
      }
    }

    // 合并
    for (let i = l; i <= r; i++) {
      arr[i] = temp[i - l];
    }
  };

  merge(nums, 0, nums.length - 1);
  return nums;
}
// @lc code=end
